package leetcode.LinkedList;

/**
 * 给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。
 *
 * 你应当保留两个分区中每个节点的初始相对位置。
 *
 * 示例:
 *
 * 输入: head = 1->4->3->2->5->2, x = 3
 * 输出: 1->2->2->4->3->5

 * @author MaoLin Wang
 * @date 2020/2/1022:50
 */
public class _86Partition {
    public static ListNode partition(ListNode head, int x) {
        if (head==null||head.next==null){
            return head;
        }

        ListNode temp=head;

        ListNode min=new ListNode(0);
        ListNode max=new ListNode(0);

        ListNode minTemp=min;
        ListNode maxTemp=max;
        while (temp!=null){
            if (temp.val<x){
                minTemp.next=temp;
                minTemp=minTemp.next;
            }else {
                maxTemp.next=temp;
                maxTemp=maxTemp.next;
            }
            temp=temp.next;
        }
        if (maxTemp.next!=null){
            maxTemp.next=null;
        }
        minTemp.next=max.next;
        return min.next;
    }
    public ListNode partition2(ListNode head, int x) {
        if (head == null){
            return  head;
        }
       ListNode min=new ListNode(-1);
       ListNode max=new ListNode(-1);
       ListNode minTemp=min;
       ListNode maxTemp=max;
       ListNode tem=head;
       while (tem!=null){
           if (tem.val<x){
               minTemp.next=tem;
               minTemp=minTemp.next;
           }else {
               maxTemp.next=tem;
               maxTemp=maxTemp.next;
           }
           ListNode next=tem.next;
           tem.next=null;
           tem=next;
       }
       minTemp.next=max.next;
       return min.next;
    }
    public static void main(String[] args) {
        ListNode l1=new ListNode(1);
        l1.next=new ListNode(4);
        l1.next.next=new ListNode(3);
        l1.next.next.next=new ListNode(2);
        l1.next.next.next.next=new ListNode(5);
        l1.next.next.next.next.next=new ListNode(2);
        ListNode partition = partition(l1, 3);
        ListNode.printNode(partition);

    }
}
